package jzoffer;

public class FindNumberIn2DArray {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix.length == 0) {
            return false;
        }
        int length=matrix.length;

        for (int i = 0; i < length; i++) {
            int xLen=matrix[i].length;
            if (xLen==0){
                continue;
            }
            if (matrix[i][0]==target||matrix[i][xLen-1]==target){
                return true;
            }else {
                if (midFind(matrix[i],target)){
                    return true;
                }
            }

        }
        return false;
    }

    public boolean midFind(int[] addr, int target) {
        if (addr.length == 0) {
            return false;
        }
        int left = 0;
        int right = addr.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (addr[mid]<target){
                left=mid+1;
            }else if (addr[mid]>target){
                right=mid-1;
            }else {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {

        int[]addr=new int[]{1,2,3,4,6,7,9,10};

        int[][]ad=new int[5][5];

        ad[0][0]=1;
        ad[0][4]=4;
        ad[2][3]=2;
        System.out.println(new FindNumberIn2DArray().findNumberIn2DArray(ad,2));
    }
}
